package com.ztom.top100;

/**
 * 编辑距离
 * <p>
 * https://leetcode-cn.com/problems/edit-distance/
 *
 * @author ZhangTao
 */
public class Code30MinDistance {

    public int minDistance2(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return -1;
        }
        return process(word1.toCharArray(), word2.toCharArray(), word1.length(), word2.length());
    }

    private int process(char[] str1, char[] str2, int l1, int l2) {
        if (l1 == 0 && l2 == 0) {
            // 俩都是空串
            return 0;
        }
        if (l1 == 0) {
            // 需要增加 l2 个字符
            return l2;
        }
        if (l2 == 0) {
            // 需要删除 l1 个字符
            return l1;
        }
        // 增加一个字符, 继续处理剩下的 l2 - 1 长度的字符
        int p1 = 1 + process(str1, str2, l1, l2 - 1);
        // 删除一个字符, 继续处理剩下 l2 长度的字符
        int p2 = 1 + process(str1, str2, l1 - 1, l2);
        // 修改一个字符, 继续处理剩下 l2 - 1 长度的字符
        int p3 = 1 + process(str1, str2, l1 - 1, l2 - 1);
        // 如果当前字符相等, 可以直接处理剩下的 l2 - 1 长度的字符
        int p4 = Integer.MAX_VALUE;
        if (str1[l1 - 1] == str2[l2 - 1]) {
            p4 = process(str1, str2, l1 - 1, l2 - 1);
        }
        // 取增删改中步数少的
        return Math.min(Math.min(p1, p2), Math.min(p3, p4));
    }

    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return -1;
        }
        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();
        int m = str1.length;
        int n = str2.length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        // 第一行: 增加 l2 个字符
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        // 第一列: 删除 l1 个字符
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}
